package com.itheima.algorithm.binarysearch;

/**
 * @author: TylerZhong
 * @description:
 */
public class BinarySearch {
    /**
     * 二分查找基础版
     * @param a - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 找到则返回索引，找不到则返回 -1
     */
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;        // 设置指针和初值
        while (i <= j) {                    // i ~ j 范围内有东西
            int m = (i + j) >>> 1;
            if (target < a[m]) {            // 目标在左边
                j = m - 1;
            } else if (a[m] < target) {     // 目标在右边
                i = m + 1;
            } else {
                return m;                   // 找到了
            }
        }
        return -1;
    }

    /**
     1 [2,3,4,5] 5 右侧没找到更差
     int i = 0, j = a.length - 1            2
     return -1;                             1
     元素个数           循环次数
     4-7                3                   floor(log_2(4)) = 2 + 1
     8-15               4                   floor(log_2(8)) = 3 + 1
     16-31              5                   floor(log_2(16)) = 4 + 1
     32-63              6                   floor(log_2(32)) = 5 + 1
     ...                ...
     循环次数L  = floor(log_2(n)) + 1

     i <= j                     L+1
     int m = (i + j) >>> 1;     L
     target < a[m]              L
     a[m] < target              L
     i = m + 1;                 L

     (floor(log_2(n)) + 1) * 5 + 4

     (3) * 5 + 4 = 19*t
     (10 + 1) * 5 + 4 = 59*5
     */



    /**
     * 二分查找改动版
     * @param a - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 找到则返回索引，找不到则返回 -1
     */
    public static int binarySearchAlternative(int[] a, int target) {
        int i = 0, j = a.length;  // 第一处改动
        while (i < j) {  // 第二处改动
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;  // 第三处改动
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    /**
     * 二分查找平衡版
     *  1. 不奢望循环内通过 m 找出目标，缩小区间直至剩1个，剩下的这个可能就是要找的（通过i）
     *  2. i 指针可能是查找目标
     *  3. j指针不可能是查找目标
     *  4. 因为1.2.3. 当区域内还剩一个元素时，表示为 j - i == 1
     *  5. 改变 i 边界时， m 可能就是目标，同时因为 2. 所以有 i = m
     *  6. 改变 j 边界时， m 已经比较过不是目标，同时因为3. 所以有 j = m
     *  7. 三分支改为二分支，循环内比较次数减少
     *
     * @param a - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 找到则返回索引，找不到则返回 -1
     */
    public static int binarySearchBalance(int[] a, int target) {
        int i = 0, j = a.length;
        while (1 < (j-i)) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
                // 10 , 18 , 22 , 30
                // 0 ,  1 ,  2 ,  3 , 4
            }
        }
        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    /**
     * 二分查找 Leftmost
     * @param a - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 找到则返回索引，找不到则返回 -1
     */
    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;        // 设置指针和初值
        int candidate = -1;
        while (i <= j) {                    // i ~ j 范围内有东西
            int m = (i + j) >>> 1;
            if (target < a[m]) {            // 目标在左边
                j = m - 1;
            } else if (a[m] < target) {     // 目标在右边
                i = m + 1;
            } else {
                // 记录候选位置
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找 Rightmost
     * @param a - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 找到则返回索引，找不到则返回 -1
     */
    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;        // 设置指针和初值
        int candidate = -1;
        while (i <= j) {                    // i ~ j 范围内有东西
            int m = (i + j) >>> 1;
            if (target < a[m]) {            // 目标在左边
                j = m - 1;
            } else if (a[m] < target) {     // 目标在右边
                i = m + 1;
            } else {
                // 记录候选位置
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }



    /**
     * 二分查找 Leftmost
     * @param a - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 返回 >= target 的最靠左索引
     */
    public static int binarySearchLeftmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;        // 设置指针和初值
        while (i <= j) {                    // i ~ j 范围内有东西
            int m = (i + j) >>> 1;
            if (target <= a[m]) {            // 目标在左边
                j = m - 1;
            } else {     // 目标在右边
                i = m + 1;
            }
        }
        return i;
    }

    /**
     * 二分查找 Rightmost
     * @param a - 待查找的升序数组
     * @param target - 待查找的目标值
     * @return 返回 <= target 的最靠右索引
     */
    public static int binarySearchRightmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;        // 设置指针和初值
        while (i <= j) {                    // i ~ j 范围内有东西
            int m = (i + j) >>> 1;
            if (target < a[m]) {            // 目标在左边
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i-1;
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] b = new int[2];
        int i = 0, j = nums.length - 1;
        while(i <= j){
            int m = (i+j) >>> 1;
            int mValue = nums[m];
            if(target <= mValue){
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        if(i >= 0 && i < nums.length && target == nums[i]){
            b[0] = i;
        } else {
            b[0] = -1;
        }

        i = 0;
        j = nums.length - 1;
        while(i <= j){
            int m = (i+j) >>> 1;
            int mValue = nums[m];
            if(target < mValue){
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        if(i >= 0 && i < nums.length && target == nums[i-1]){
            b[1] = i - 1;
        } else {
            b[1] = -1;
        }
        return b;
    }

    public static void main(String[] args) {
        int[] a = {5,7,7,8,8,10};
//        assertEquals("[3,4]", searchRange(a, 8));
    }

}
